{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def threeSum(self, nums: List[int]) -> List[List[int]]:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        ans = list()\n",
    "        \n",
    "        # 枚举 a\n",
    "        for first in range(n):\n",
    "            # 需要和上一次枚举的数不相同\n",
    "            if first > 0 and nums[first] == nums[first - 1]:\n",
    "                continue\n",
    "            # c 对应的指针初始指向数组的最右端\n",
    "            third = n - 1\n",
    "            target = -nums[first]\n",
    "            # 枚举 b\n",
    "            for second in range(first + 1, n):\n",
    "                # 需要和上一次枚举的数不相同\n",
    "                if second > first + 1 and nums[second] == nums[second - 1]:\n",
    "                    continue\n",
    "                # 需要保证 b 的指针在 c 的指针的左侧\n",
    "                while second < third and nums[second] + nums[third] > target:\n",
    "                    third -= 1\n",
    "                # 如果指针重合，随着 b 后续的增加\n",
    "                # 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环\n",
    "                if second == third:\n",
    "                    break\n",
    "                if nums[second] + nums[third] == target:\n",
    "                    ans.append([nums[first], nums[second], nums[third]])\n",
    "        \n",
    "        return ans"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "pylearn",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "name": "python",
   "version": "3.10.14"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
